package gold.digger;

import java.util.ArrayList;
import java.util.List;

/**
 * Created by fanzhenyu02 on 2020/6/27.
 * common problem solver template.
 */
public class LC558 {
    public long startExecuteTime = System.currentTimeMillis();


    // Definition for a QuadTree node.
    class Node {
        public boolean val;
        public boolean isLeaf;
        public Node topLeft;
        public Node topRight;
        public Node bottomLeft;
        public Node bottomRight;

        public Node() {
        }

        public Node(boolean _val, boolean _isLeaf, Node _topLeft, Node _topRight, Node _bottomLeft, Node _bottomRight) {
            val = _val;
            isLeaf = _isLeaf;
            topLeft = _topLeft;
            topRight = _topRight;
            bottomLeft = _bottomLeft;
            bottomRight = _bottomRight;
        }
    }

    class Solution {
        public Node intersect(Node quadTree1, Node quadTree2) {
            return intersectRecur(quadTree1, quadTree2);
        }

        public Node intersectRecur(Node q1, Node q2) {
            if (q1.isLeaf && q2.isLeaf)
                return new Node(q1.val || q2.val, true, null, null, null, null);

            if (!q1.isLeaf && !q2.isLeaf) {
                Node topLeft = intersectRecur(q1.topLeft, q2.topLeft);
                Node topRight = intersectRecur(q1.topRight, q2.topRight);
                Node bottomLeft = intersectRecur(q1.bottomLeft, q2.bottomLeft);
                Node bottomRight = intersectRecur(q1.bottomRight, q2.bottomRight);
                if (topLeft.isLeaf && topRight.isLeaf && bottomLeft.isLeaf && bottomRight.isLeaf && topLeft.val == topRight.val && bottomLeft.val == bottomRight.val && topRight.val == bottomRight.val) {
                    return new Node(topLeft.val, true, null, null, null, null);
                } else {
                    //只要有一个不是叶子，全返回
                    return new Node(false, false, topLeft, topRight, bottomLeft, bottomRight);
                }
            }

            if (q1.isLeaf) {
                if (q1.val) {
                    //q1全是1，则q2不需要看，都会被覆盖为1
                    return new Node(true, true, null, null, null, null);
                } else {
                    return q2;
                }
            } else {
                return intersectRecur(q2, q1);
            }
        }
    }


    public void run() {
        Solution solution = new Solution();
        System.out.println(solution.toString());
    }

    public static void main(String[] args) throws Exception {
        LC558 an = new LC558();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
